{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ls = lambda k: 2 * k\n",
    "rs = lambda k: 2 * k + 1\n",
    "\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, array):  # element index starts from 0\n",
    "        self.n = len(array)\n",
    "        self.size = 4 * self.n\n",
    "\n",
    "        self.array = [0] + array\n",
    "\n",
    "        self.left, self.right = [0] * self.size, [0] * self.size\n",
    "        self.value, self.tag = [0] * self.size, [0] * self.size\n",
    "\n",
    "        self.build(1, 1, self.n)\n",
    "\n",
    "    def m(self, k):\n",
    "        return (self.left[k] + self.right[k]) // 2\n",
    "\n",
    "    def length(self, k):\n",
    "        return self.right[k] - self.left[k] + 1\n",
    "\n",
    "    def update(self, k, delt):\n",
    "        # self.tag[k] += delt\n",
    "        # self.value[k] += delt * self.length(k)\n",
    "        pass\n",
    "\n",
    "    def push_up(self, k):\n",
    "        # self.value[k] = self.value[ls(k)] + self.value[rs(k)]\n",
    "        pass\n",
    "\n",
    "    def push_down(self, k):\n",
    "        delt = self.tag[k]\n",
    "        self.update(ls(k), delt), self.update(rs(k), delt)\n",
    "        self.tag[k] = 0\n",
    "\n",
    "    def build(self, k, l, r):\n",
    "        self.left[k], self.right[k] = l, r\n",
    "\n",
    "        if l == r:\n",
    "            self.value[k] = self.array[l]\n",
    "        else:\n",
    "            m = self.m(k)\n",
    "\n",
    "            self.build(ls(k), l, m)\n",
    "            self.build(rs(k), m + 1, r)\n",
    "            self.push_up(k)\n",
    "\n",
    "    def _modify(self, k, a, b, delt):\n",
    "        if a <= self.left[k] and self.right[k] <= b:\n",
    "            self.update(k, delt)\n",
    "        else:\n",
    "            self.push_down(k)\n",
    "            m = self.m(k)\n",
    "\n",
    "            if a <= m:\n",
    "                self._modify(ls(k), a, b, delt)\n",
    "            if b > m:\n",
    "                self._modify(rs(k), a, b, delt)\n",
    "            self.push_up(k)\n",
    "\n",
    "    def _query(self, k, a, b):\n",
    "        res = 0\n",
    "\n",
    "        if a <= self.left[k] and self.right[k] <= b:\n",
    "            return self.value[k]\n",
    "\n",
    "        self.push_down(k)\n",
    "        m = self.m(k)\n",
    "\n",
    "        if a <= m:\n",
    "            res += self._query(ls(k), a, b)\n",
    "        if m < b:\n",
    "            res += self._query(rs(k), a, b)\n",
    "\n",
    "        return res\n",
    "\n",
    "    def modify(self, a, b, delt):\n",
    "        self._modify(1, a, b, delt)\n",
    "\n",
    "    def query(self, a, b):\n",
    "        return self._query(1, a, b)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.9.12"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "3a176caed2e623e3a36a87b094ae4f1cc68623d3a88a2d36a2ea84f7c5d7277a"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
